package com.leetcode.专项突破.二叉树;

import com.leetcode.common.model.TreeNode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-04-10 15:29
 */
public class PostorderTraversal {

  public static void main(String[] args) {
    Solution solution = new Solution();
    TreeNode node1 = new TreeNode(1);
    TreeNode node2 = new TreeNode(2);
    TreeNode node3 = new TreeNode(3);
    node1.right = node2;
    node2.left = node3;
    List<Integer> list = solution.postorderTraversal(node1);
    System.out.println(list);
  }

  static
  class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
//      List<Integer> answers = new ArrayList<>();
//      postorderTraversalWithRecursion(root, answers);
//      return answers;
//      return postorderTraversalWithStack(root);
      return postorderTraversalWith2Stack(root);
    }

    private void postorderTraversalWithRecursion(TreeNode root, List<Integer> answers) {
      if (root == null) {
        return;
      }
      postorderTraversalWithRecursion(root.left, answers);
      postorderTraversalWithRecursion(root.right, answers);
      answers.add(root.val);
    }

    private List<Integer> postorderTraversalWith2Stack(TreeNode root) {
      List<Integer> answers = new ArrayList<>();
      if (root == null) {
        return answers;
      }
      Deque<TreeNode> stack = new ArrayDeque<>();
      Deque<TreeNode> answerStack = new ArrayDeque<>();
      stack.push(root);
      while (!stack.isEmpty()) {
        root = stack.pop();
        answerStack.push(root);
        if (root.left != null) {
          stack.push(root.left);
        }
        if (root.right != null) {
          stack.push(root.right);
        }
      }
      while (!answerStack.isEmpty()) {
        answers.add(answerStack.pop().val);
      }
      return answers;
    }

    private List<Integer> postorderTraversalWithStack(TreeNode root) {
      List<Integer> answers = new ArrayList<>();
      if (root == null) {
        return answers;
      }

      Deque<TreeNode> stack = new ArrayDeque<>();
      TreeNode prePop = null;
      while (root != null || !stack.isEmpty()) {
        if (root != null) {
          stack.push(root);
          root = root.left;
        } else if (stack.peek().right != prePop && stack.peek().right != null) {
          root = stack.peek().right;
        } else {
          TreeNode pop = stack.pop();
          answers.add(pop.val);
          prePop = pop;
        }
      }
      return answers;
    }
  }

}
